package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.*;

/**
 * @author zhangjy
 * @description 二叉搜索树中的众数
 * <p>
 * 该题允许BST有重复元素
 * @date 2025/4/24 23:21
 */
public class FindMode_501 {

    public static void main(String[] args) {
        FindMode_501 findMode501 = new FindMode_501();

        TreeNode five = new TreeNode(1);
        TreeNode four = new TreeNode(1);
        TreeNode three = new TreeNode(2, four, five);
        TreeNode two = new TreeNode(2, three, null);
        TreeNode one = new TreeNode(1, null, two);

        Arrays.stream(findMode501.findMode2(one)).forEach(System.out::println);
        Arrays.stream(findMode501.findMode3(one)).forEach(System.out::println);
    }

    /**
     * 参考dmsxl: 递归-dfs-中序-双指针
     * <p>
     * 双指针优化为 S(n) = O(1)
     */
    // 单个元素出现的次数
    int count3 = 0;

    // 所有元素出现的最大次数
    int maxCount3 = 0;

    // 前一个节点（中序遍历结果中的前一个）
    TreeNode pre = null;

    // 记录众数
    List<Integer> vals = new ArrayList<>();

    public int[] findMode3(TreeNode root) {
        dfs3(root);

        int[] ans = new int[vals.size()];
        for (int i = 0; i < vals.size(); i++) {
            ans[i] = vals.get(i);
        }
        return ans;
    }

    public void dfs3(TreeNode node) {
        if (node == null) return;

        // 左
        dfs3(node.left);

        // 中
        // 记录元素出现的次数
        if (pre == null) {
            count3 = 1;
        } else if (pre.val == node.val) {
            count3++;
        } else {
            // 与前一个节点值不同, 新元素重新开始计数
            count3 = 1;
        }
        // 更新pre
        pre = node;

        // 当前元素的出现次数和所有元素最大次数相等,则直接记录; 反之, 先清空之前记录的结果,再记录当前元素
        if (count3 == maxCount3) {
            vals.add(node.val);
        }
        // 注意,这里不能接上面if的else, 因为还有 count3<maxCount3 , 此时的节点值并不是要找的众数, 所以不需要记录 也不用清空vals
        if (count3 > maxCount3) {
            // 先清空
            vals = new ArrayList<>();
            // 再记录
            vals.add(node.val);

            // 更新maxCount
            maxCount3 = count3;
        }

        // 右
        dfs3(node.right);

    }

    /**
     * 个解
     * <p>
     * 思路: 递归过程就记录所有众数节点值
     * <p>
     * 不足: 还是没用到BST的中序遍历结果有序特性
     */
    // key=节点值 value=出现次数
    Map<Integer, Integer> numCountMap2 = new HashMap<>();

    // key=众数节点值 value=出现次数
    Map<Integer, Integer> numMaxCountMap2 = new HashMap<>();

    // 最高出现次数
    int maxCount2 = 1;

    public int[] findMode2(TreeNode root) {
        if (root == null) return null;

        dfs2(root);

        // 将所有众数记录到数组
        int[] ans = new int[numMaxCountMap2.size()];
        Set<Map.Entry<Integer, Integer>> entries = numMaxCountMap2.entrySet();
        int i = 0;
        for (Map.Entry<Integer, Integer> entry : entries) {
            ans[i] = entry.getKey();
            i++;
        }
        return ans;
    }

    public void dfs2(TreeNode node) {
        if (node == null) return;

        // 左
        dfs2(node.left);

        // 中
        // 1.统计每个数出现的次数
        int count = 1;
        if (numCountMap2.containsKey(node.val)) {
            count = numCountMap2.get(node.val) + 1;
        }
        numCountMap2.put(node.val, count);
        // 2.记录最大众数和节点值关系,以及哪些节点是最大众数
        if (count == maxCount2) {
            numMaxCountMap2.put(node.val, maxCount2);
        }
        if (count > maxCount2) {
            // 先清空
            numMaxCountMap2 = new HashMap<>();
            // 再记录当前元素
            numMaxCountMap2.put(node.val, maxCount2);
            maxCount2 = count;
        }

        // 右
        dfs2(node.right);
    }

    /**
     * 个解
     * <p>
     * 不足: 没用到BST的中序遍历结果有序特性.
     * <p>
     * T(n) = O(n).
     * S(n) = O(n); 哈希表占用空间
     */
    Map<Integer, Integer> numCountMap = new HashMap<>();

    public int[] findMode(TreeNode root) {
        if (root == null) return null;

        dfs(root);

        Set<Map.Entry<Integer, Integer>> entries = numCountMap.entrySet();
        // 统计众数的数量
        int maxCount = 0, count = 0;
        for (Map.Entry<Integer, Integer> entry : entries) {
            if (entry.getValue() > maxCount) {
                // 出现更大的众数
                count = 1;
                maxCount = entry.getValue();
            } else if (entry.getValue() == maxCount) {
                // 记录目前众数的数量
                count++;
            }
        }

        // 记录到数组
        int[] ans = new int[count];
        int i = 0;
        for (Map.Entry<Integer, Integer> entry : entries) {
            if (entry.getValue() == maxCount) {
                ans[i] = entry.getKey();
                i++;
            }
        }
        return ans;
    }

    public void dfs(TreeNode node) {
        if (node == null) return;

        // 左
        dfs(node.left);

        // 中
        // 统计每个数出现的次数
        int count = 1;
        if (numCountMap.containsKey(node.val)) {
            count = numCountMap.get(node.val) + 1;
        }
        numCountMap.put(node.val, count);

        // 右
        dfs(node.right);
    }

}
